package nowcoder.recursive;

/*
描述
给定一个字符串s，长度为n，求s的所有子序列
1.子序列: 指一个字符串删掉部分字符（也可以不删）形成的字符串，可以是不连续的，比如"abcde"的子序列可以有"ace","ad"等等
2.将所有的子序列的结果返回为一个字符串数组
3.字符串里面可能有重复字符，但是返回的子序列不能有重复的子序列，比如"aab"的子序列只有"","a","aa","aab","ab","b"，不能存在2个相同的"ab"
4.返回字符串数组里面的顺序可以不唯一

数据范围:
0
<
=
𝑠
.
𝑙
𝑒
𝑛
𝑔
𝑡
ℎ
<
=
16
0<=s.length<=16

要求:时间复杂度为
𝑂
(
2
𝑛
)
O(2
n
 )

示例1
输入：
"ab"
复制
返回值：
["","a","ab","b"]
复制
说明：
返回["","b","a","ab"]也是可以的，视为正确，顺序不唯一
示例2
输入：
"dbcq"
复制
返回值：
["","b","bc","bcq","bq","c","cq","d","db","dbc","dbcq","dbq","dc","dcq","dq","q"]
复制
示例3
输入：
"aab"
复制
返回值：
["","a","aa","aab","ab","b"]
复制
说明：
返回的字符串数组里面不能存在"ab","ab"这样2个相同的子序列
 */

import java.util.HashSet;
import java.util.Set;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param s string字符串
     * @return string字符串一维数组
     */
    public String[] generatePermutation(String s) {
        // write code here
        char[] sCharArr = s.toCharArray();
        Set<String> r = new HashSet<>();
        f(sCharArr, 0, new StringBuilder(), r);
        return r.toArray(new String[]{});
    }

    public void f(char[] s, int curIndex, StringBuilder path, Set<String> r) {
        if (curIndex == s.length) {
            System.out.println("path = " + path.toString());
            r.add(path.toString());
        } else {
            path.append(s[curIndex]);
            f(s, curIndex + 1, path, r);
            path.deleteCharAt(path.length() - 1);
            f(s, curIndex + 1, path, r);
        }
    }

    public String[] generatePermutation2(String s) {
        // write code here
        char[] sCharArr = s.toCharArray();
        Set<String> r = new HashSet<>();
        char[] tempChArr = new char[sCharArr.length];
        f2(sCharArr, 0, 0, tempChArr, r);
        return r.toArray(new String[]{});
    }

    public void f2(char[] s, int curIndex, int size, char[] tempChArr, Set<String> r) {
        if (curIndex == s.length) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < size; i++) {
                stringBuilder.append(tempChArr[i]);
            }
            r.add(stringBuilder.toString());
        } else {
            tempChArr[size] = s[curIndex];
            f2(s, curIndex + 1, size + 1, tempChArr, r);
            f2(s, curIndex + 1, size, tempChArr, r);
        }
    }

    public static void main(String[] args) {
//        String[] abcs = new Solution().generatePermutation("abc");
//        for (String abc : abcs) {
//            System.out.println("abc = " + abc);
//        }

        String[] abcs = new Solution().generatePermutation2("abc");
        for (String abc : abcs) {
            System.out.println("abc = " + abc);
        }
    }
}